1847D - Professor Higashikata - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, q;
int l[200005], r[200005], rnk[200005];
vector <int> v, sv;
int nxt[200005];
bool s[200005];

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<int> const &a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

int getNext(int x){
    if(nxt[x] == x)
        return x;
    return nxt[x] = getNext(nxt[x]);
}

int main(){
    cin >> n >> m >> q;
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        char c;
        cin >> c;
        s[i] = (c == '1');
        cnt += s[i];
        nxt[i] = i;
    }
    nxt[n+1] = n+1;

    int t = 0;

    for(int i = 0; i < m; i++)
        cin >> l[i] >> r[i];
    l[m] = 1; r[m] = n;

    for(int i = 0; i < m; i++){
        for(int j = getNext(l[i]); j <= r[i]; j = getNext(j+1)){
            rnk[j] = t++;
            v.push_back(j);
            sv.push_back(s[j]);
            nxt[j] = j+1;
        }
    }

    for(int i = 1; i <= n; i++)
        if(nxt[i] == i)
            rnk[i] = t++;

    FenwickTree F(sv);
    //for(auto x : sv)
    //    cout << x << " ";

    for(int i = 0; i < q; i++){
        int x;
        cin >> x;
        int delta = (s[x] ? -1 : 1);
        
        cnt += delta;
        s[x] ^= 1;
        if(nxt[x] != x)
            F.add(rnk[x], delta);
        int bound = min(cnt, (int)sv.size());
        cout << bound - F.sum(bound-1) << endl;
    }
}